package cn.com.mdx.sort.heapsort.priorityqueue;

import cn.com.mdx.sort.SortUtils;

import java.util.Random;

/**
 * <p> 不排序数组实现
 * 存入数据时间复杂度：1
 * 获取数据时间复杂度：N
 * 获取最大值的时间复杂度：N
 *
 * @author ：huangy
 * @date ：Created in 2020/10/13 4:40 下午
 */
@SuppressWarnings(value = {"unchecked"})
public class UnorderedMaxPQ<Key extends Comparable<Key>> {
    //存放数据的数组
    private final Key[] pq;
    //数组的容量
    private int N;

    public UnorderedMaxPQ(int capacity) {
        pq = (Key[]) new Comparable[capacity];
    }

    /**
     * @return boolean true 为空 false 不为空
     * @Author huangy
     * @description //TODO 队列是否为空
     * @date 5:03 下午 2020/10/14
     **/
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * @param key 插入队列中的数据
     * @return void
     * @Author huangy
     * @description //TODO 向队列中插入数据
     * @date 5:04 下午 2020/10/14
     **/
    public void insert(Key key) {
        pq[N++] = key;
    }

    /**
     * @return Key 队列中最大值
     * @Author huangy
     * @description //TODO 删除队列最大值
     * @date 5:06 下午 2020/10/14
     **/
    public Key delMax() {
        int max = 0;
        for (int i = 0; i < N; i++) if (SortUtils.great(pq[i], pq[max])) max = i;
        SortUtils.exChange(pq, max, N - 1);
        return pq[--N];
    }

    /**
     * @return Key 队列最大值
     * @Author huangy
     * @description //TODO 队列最大值
     * @date 5:37 下午 2020/10/14
     **/
    public Key max() {
        int max = 0;
        for (int i = 0; i < N; i++) if (SortUtils.great(pq[i], pq[max])) max = i;
        return pq[max];
    }

    public static void main(String[] args) {
        Random random = new Random();
        int key = 50;
        UnorderedMaxPQ<Integer> unorderedMaxPQ = new UnorderedMaxPQ<>(key);
        //向队列中添加元素
        for (int i = 0; i < key; i++) unorderedMaxPQ.insert(random.nextInt(key));
        //删除队列中元素
        for (int i = 0; i < key; i++) {
            System.out.println();
            System.out.println(unorderedMaxPQ.delMax());
        }
    }

}
